package com.my.datastructure;

/**
 * 单向环形链表解决约瑟夫问题
 * 小美有一天想玩丢手绢，但是TA就一个人怎么办呢？
 *
 * @author zhangshuaiyin
 * @date 2021-04-12 16:26
 */
public class CircleSingleLinkedList {
    private Boy first = new Boy(1);

    /**
     * 向约瑟夫环添加成员
     *
     * @param nums 成员个数
     */
    public void init(int nums) {
        if (nums < 2) {
            throw new RuntimeException("成员个数必须大于1");
        }
        Boy temp = first;
        for (int i = 2; i <= nums; i++) {
            Boy boy = new Boy(i);
            temp.next = boy;
            boy.next = first;
            temp = boy;
        }
    }

    /**
     * 遍历链表查看元素
     */
    public void list() {
        Boy temp = first;
        System.out.print("小孩的编号: ");
        do {
            System.out.printf("%d\t", (temp.no));
        } while ((temp = temp.next) != first);
    }

    /**
     * 根据用户的输入，计算小孩出圈的顺序
     *
     * @param startNo 从第几个小孩开始报数
     * @param count   报数次数
     * @param nums    小孩个数
     */
    public void removeByWt(int startNo, int count, int nums) {
        if (startNo < 1 || startNo > nums) {
            throw new RuntimeException("参数输入有误~");
        }
        Boy temp = first;
        //找到第一个报数小孩的位置
        for (int i = 0; i < startNo - 1; i++) {
            temp = temp.next;
        }
        while (true) {
            if (temp == temp.next) {
                //就剩下一个小孩了
                System.out.printf("小孩%d 出圈\n", temp.no);
                return;
            }
            //报数，找到要出圈的小孩的前一个小孩
            for (int i = 0; i < count - 2; i++) {
                temp = temp.next;
            }
            System.out.printf("小孩%d 出圈\n", temp.next.no);
            //将小孩出圈
            temp.next = temp.next.next;
            //从出圈小孩的下一个开始重新计数
            temp = temp.next;
        }
    }
    /**
     * 根据用户的输入，计算小孩出圈的顺序
     *
     * @param startNo 从第几个小孩开始报数
     * @param count   报数次数
     * @param nums    小孩个数
     */
    public void remove(int startNo, int count, int nums) {
        if (startNo < 1 || startNo > nums) {
            throw new RuntimeException("参数输入有误~");
        }
        // 创建辅助变量helper，初始指向环形链表的最后一个节点
        Boy helper = first;
        while (helper.next != first) {
            helper = helper.next;
        }
        // 报数前，先让 first 和 helper 移动第一个报数小孩的前一个位置
        for (int i = 0; i < startNo - 1; i++) {
            first = first.next;
            helper = helper.next;
        }
        // 开始报数，helper == first 说明只剩一个成员
        while (helper != first) {
            // 让 first 和 helper 移动 报数次数-1 次，这时 first 就是要出圈的小孩
            for (int i = 0; i < count - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            System.out.printf("小孩%d 出圈\n", first.no);
            //这时将 first 指向的小孩节点出圈
            first = first.next;
            helper.next = first;
        }
        System.out.printf("小孩%d 出圈\n", first.no);
    }
}